{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert Binary Search Tree to Sorted Doubly Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #linked-list #binary-tree #doubly-linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #链表 #二叉树 #双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: treeToDoublyList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将二叉搜索树转化为排序的双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>将一个 <strong>二叉搜索树</strong> 就地转化为一个 <strong>已排序的双向循环链表</strong> 。</p>\n",
    "\n",
    "<p>对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。</p>\n",
    "\n",
    "<p>特别地，我们希望可以 <strong>就地</strong> 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,5,1,3] \n",
    "\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png\" style=\"width: 400px;\" />\n",
    "<strong>输出：</strong>[1,2,3,4,5]\n",
    "\n",
    "<strong>解释：</strong>下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/bstdllreturnbst.png\" style=\"width: 400px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3]\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>输入是空树，所以输出也是空链表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-1000 <= Node.val <= 1000</code></li>\n",
    "\t<li><code>Node.left.val < Node.val < Node.right.val</code></li>\n",
    "\t<li><code>Node.val</code> 的所有值都是独一无二的</li>\n",
    "\t<li><code>0 <= Number of Nodes <= 2000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-binary-search-tree-to-sorted-doubly-linked-list](https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-binary-search-tree-to-sorted-doubly-linked-list](https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,1,3]', '[2,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left, right):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        head = Node(-1, None, None)\n",
    "\n",
    "        if not root:\n",
    "        \treturn None\n",
    "\n",
    "        node = root\n",
    "        stack = []\n",
    "        smallestNode = None\n",
    "        largestNode = None\n",
    "        prev = Node(-1,None, None)\n",
    "        while stack or node:\n",
    "        \twhile node:\n",
    "        \t\tstack.append(node)\n",
    "        \t\tnode = node.left\n",
    "        \t\t\n",
    "        \tnode = stack.pop()\n",
    "        \tif smallestNode == None:\n",
    "        \t\tsmallestNode = node\n",
    "        \tlargestNode = node\n",
    "        \tprev.right = node\n",
    "        \tnode.left = prev\n",
    "        \tprev = node\n",
    "        \tnode = node.right\n",
    "        smallestNode.left = largestNode\n",
    "        largestNode.right = smallestNode\n",
    "        return smallestNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = [] # []\n",
    "        first = None # all the logic about first\n",
    "        pre = None\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if first is None:\n",
    "                first = root\n",
    "            else:\n",
    "                root.left = pre\n",
    "                pre.right = root\n",
    "            pre = root\n",
    "            root = root.right\n",
    "        pre.right = first # 3 lines\n",
    "        first.left = pre\n",
    "        return first\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "        # 中序遍历的非递归\n",
    "        stack = []\n",
    "        p = root\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            # 改变左右方向\n",
    "            prev.right = p\n",
    "            p.left = prev\n",
    "            # 改变先前节点\n",
    "            prev = p\n",
    "            p = p.right\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return\n",
    "        prev, head = None, None\n",
    "        s = []\n",
    "        while s or root:\n",
    "            while root:\n",
    "                s.append(root)\n",
    "                root = root.left\n",
    "            root = s.pop()\n",
    "            if not head:\n",
    "                head = root\n",
    "            if prev:\n",
    "                prev.right = root\n",
    "                root.left = prev\n",
    "            prev = root\n",
    "            root = root.right\n",
    "        head.left = prev\n",
    "        prev.right = head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        stack = []\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            root = root.left\n",
    "        ans = pre = None\n",
    "        while stack:\n",
    "            if not ans:  #初始化\n",
    "                ans = pre = stack.pop()\n",
    "                if pre.right:\n",
    "                    cur = pre.right\n",
    "                    while cur:\n",
    "                        stack.append(cur)\n",
    "                        cur = cur.left\n",
    "                continue\n",
    "            cur = stack.pop()\n",
    "            pre.right, cur.left = cur, pre  #更新指向\n",
    "            pre = pre.right\n",
    "            if cur.right:\n",
    "                cur = cur.right\n",
    "                while cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                \n",
    "        ans.left, pre.right = pre, ans #最后将首尾相连\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        first = None\n",
    "        pre = None\n",
    "        stack = []\n",
    "        while stack or root: # or          \n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if first:\n",
    "                pre.right = root\n",
    "                root.left = pre\n",
    "            else:\n",
    "                first = root\n",
    "            pre = root\n",
    "            root = root.right\n",
    "            \n",
    "        pre.right = first\n",
    "        first.left = pre\n",
    "        return first\n",
    "\n",
    "       \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        newRoot = None\n",
    "        pre = None\n",
    "        cur = root\n",
    "        stack = []\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if pre:\n",
    "                pre.right = cur\n",
    "            else:\n",
    "                newRoot = cur \n",
    "            cur.left = pre\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        \n",
    "        pre.right = newRoot\n",
    "        newRoot.left = pre\n",
    "        return newRoot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        self.prev = None\n",
    "        self.head = None\n",
    "        curNode = root\n",
    "        stack = []\n",
    "        while curNode or stack:\n",
    "            while curNode:\n",
    "                stack.append(curNode)\n",
    "                curNode = curNode.left\n",
    "        \n",
    "            curNode = stack.pop()\n",
    "            if self.prev:\n",
    "                self.prev.right = curNode\n",
    "                curNode.left = self.prev\n",
    "            else:\n",
    "                self.head = curNode\n",
    "            self.prev = curNode\n",
    "            \n",
    "            curNode = curNode.right\n",
    "            \n",
    "\n",
    "        self.head.left = self.prev\n",
    "        self.prev.right = self.head\n",
    "\n",
    "        return self.head\n",
    "            \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        def _inOrder(root):\n",
    "            if root.left:\n",
    "                _inOrder(root.left)\n",
    "            \n",
    "            if self.prev:\n",
    "                self.prev.right = root\n",
    "                root.left = self.prev\n",
    "            else:\n",
    "                self.head = root\n",
    "            self.prev = root\n",
    "            if root.right:\n",
    "                _inOrder(root.right)\n",
    "\n",
    "        \n",
    "        _inOrder(root)\n",
    "        self.head.left = self.prev\n",
    "        self.prev.right = self.head\n",
    "\n",
    "        return self.head\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "'''\n",
    "in-Order\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root: return root\n",
    "        stack, cur, sentinal = list(), root, Node()\n",
    "        prev = sentinal\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            prev.right = cur\n",
    "            cur.left = prev\n",
    "            prev = cur\n",
    "            cur = cur.right\n",
    "        prev.right = sentinal.right\n",
    "        sentinal.right.left = prev\n",
    "        return sentinal.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        stack = []\n",
    "        cur = root\n",
    "        head = None  # To store the smallest element of the linked list\n",
    "        prev = None\n",
    "\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "            popNode = stack.pop()\n",
    "            if prev:\n",
    "                prev.right = popNode\n",
    "            else:\n",
    "                head = popNode  # Set head to the leftmost node as it's the smallest\n",
    "\n",
    "            popNode.left = prev\n",
    "            prev = popNode\n",
    "            cur = popNode.right\n",
    "\n",
    "        # Connect the head and tail to make it a circular doubly-linked list\n",
    "        head.left = prev\n",
    "        prev.right = head\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        first = None\n",
    "        pre = None\n",
    "        stack = []\n",
    "        while stack or root: # or          \n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if first:\n",
    "                pre.right = root\n",
    "                root.left = pre\n",
    "            else:\n",
    "                first = root\n",
    "            pre = root\n",
    "            root = root.right\n",
    "            \n",
    "        pre.right = first\n",
    "        first.left = pre\n",
    "        return first\n",
    "\n",
    "       \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root \n",
    "\n",
    "        dummyHead = Node(0)\n",
    "        pointer = dummyHead\n",
    "        stack = deque() \n",
    "        cur = root \n",
    "        while cur:\n",
    "            stack.append(cur)\n",
    "            cur = cur.left \n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pointer.right = cur \n",
    "            cur.left = pointer\n",
    "            pointer = cur \n",
    "            cur = cur.right \n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left \n",
    "        \n",
    "        pointer.right = dummyHead.right \n",
    "        dummyHead.right.left = pointer\n",
    "        return dummyHead.right \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        stack = []\n",
    "        node = root\n",
    "        pre = None\n",
    "        foundNewRoot = False\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        while node or stack:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            if not foundNewRoot:\n",
    "                foundNewRoot = True\n",
    "                root = node\n",
    "            \n",
    "            if pre:\n",
    "                node.left = pre\n",
    "                pre.right = node\n",
    "            # print(node.val, node.left.val if node.left else 'None')\n",
    "            # node.left = pre\n",
    "            pre = node\n",
    "            node = node.right\n",
    "\n",
    "        root.left = pre\n",
    "        pre.right = root\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    # 非递归，中序遍历\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "        # 中序遍历的非递归\n",
    "        stack = []\n",
    "        p = root\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            # 改变左右方向\n",
    "            prev.right = p\n",
    "            p.left = prev\n",
    "            # 改变先前节点\n",
    "            prev = p\n",
    "            p = p.right\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n",
    "        \n",
    "    # 递归，中序遍历\n",
    "    def treeToDoublyList2(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "\n",
    "        # 中序遍历的递归\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = []\n",
    "        cur = root\n",
    "        foundNewRoot = False\n",
    "        pre = None\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if not foundNewRoot:\n",
    "                foundNewRoot = True\n",
    "                root = cur\n",
    "            if pre:\n",
    "                pre.right = cur\n",
    "            cur.left = pre\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "\n",
    "        pre.right = root\n",
    "        root.left = pre\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return \n",
    "        head = Node(-1, None, None)\n",
    "        pre = head\n",
    "        p = root\n",
    "        stack = []\n",
    "        while stack or p:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            pre.right = p\n",
    "            p.left = pre\n",
    "            pre = p\n",
    "            p = p.right\n",
    "        pre.right = head.right\n",
    "        head.right.left = pre\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "        # 中序遍历的非递归\n",
    "        stack = []\n",
    "        p = root\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            # 改变左右方向\n",
    "            prev.right = p\n",
    "            p.left = prev\n",
    "            # 改变先前节点\n",
    "            prev = p\n",
    "            p = p.right\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "\n",
    "        # 中序遍历的递归\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return \n",
    "        head = Node(-1,None,None)\n",
    "        prev = head\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # inorder traverse -> list -> double linked list\n",
    "        if not root: return\n",
    "        dummy = Node(-1)\n",
    "        pre = dummy\n",
    "        def inorderTraverse(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            inorderTraverse(root.left)\n",
    "\n",
    "            pre.right = root\n",
    "            root.left = pre\n",
    "            pre = pre.right \n",
    "            \n",
    "            inorderTraverse(root.right)\n",
    "        \n",
    "        inorderTraverse(root)\n",
    "        # remove dummy node, break bi-direction link\n",
    "        # pre(tail) = dummy = dummy.right\n",
    "        dummy.right.left = pre\n",
    "        pre.right = dummy.right\n",
    "         \n",
    "        return pre.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root: return\n",
    "\n",
    "        head = Node(0)\n",
    "        prev = head\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        \n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(cur):\n",
    "            if not cur:return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            else:\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right) \n",
    "\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left = self.pre\n",
    "        self.pre.right = self.head\n",
    "        return self.head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:    return None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            \n",
    "            Lstart, Lend = dfs(root.left)\n",
    "            Rstart, Rend = dfs(root.right)\n",
    "            ansL = ansR = root\n",
    "            if Lstart:\n",
    "                root.left, Lend.right = Lend, root\n",
    "                ansL = Lstart\n",
    "            if Rstart:\n",
    "                root.right, Rstart.left = Rstart, root\n",
    "                ansR = Rend\n",
    "            return ansL, ansR\n",
    "        \n",
    "        ansL, ansR = dfs(root)\n",
    "        ansL.left, ansR.right = ansR, ansL\n",
    "        return ansL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        head, tail = None, None\n",
    "        pre = head\n",
    "        def dfs(node):\n",
    "            nonlocal head, tail, pre\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            if not head:\n",
    "                head = node\n",
    "            tail = node\n",
    "            if pre:\n",
    "                pre.right = node\n",
    "                node.left = pre\n",
    "            pre = node\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        head.left = tail\n",
    "        tail.right = head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # https://www.youtube.com/watch?v=H5zop8o-HG4&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3\n",
    "\n",
    "        #结合linked list + bst\n",
    "\n",
    "        #两种方法， 递归+  iterative\n",
    "\n",
    "        #  dfs 三种遍历： \n",
    "        #  in order中序： left - node -right\n",
    "        #  preorder 前序： node -left -right\n",
    "        #  post order: left - right - node\n",
    "\n",
    "        #由于给你的是bst， 左小右大，所以用中序遍历。拿出来一定是排序好的节点：left-node-right\n",
    "\n",
    "        #另外是double linked list,需要prev。 利用in order遍历到bst的最左下（最小值），\n",
    "        # 1. base case ： if not current: return None\n",
    "\n",
    "        # 2. 对当前节点的left 开始递归\n",
    "        # 如果当前节点的prev是空的，那说明走到左下角头（第一次递归到头一定是左下角）那他就是head \n",
    "        # 如果此时prev是空，那他就是head嘛\n",
    "        # 如果prev不是空，那就link： prev-><-current\n",
    "        # 然后就把prev变成当前点:继续向右走（当继续下一个点的时候，当前点就会是下一个点的prev）--prev先走--要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "        # 然后对当前节点右侧调用递归\n",
    "\n",
    "        #遍历完之后，表示doulbe linked list 完成\n",
    "\n",
    "        #主要要变成circular， 也就是头尾也相连\n",
    "        #最后return head\n",
    "\n",
    "\n",
    "        #先移动prev，在移动current\n",
    "\n",
    "\n",
    "####1 recursi\n",
    "\n",
    "    #     if not root: #首先在外面也需要一个，如果根节点是空的，直接啥也不用干\n",
    "    #         return\n",
    "\n",
    "\n",
    "    #     #这俩都是空的一开始\n",
    "    #     self.head = None # global variable\n",
    "    #     self.prev = None #是node哦，node有val， left，right\n",
    "\n",
    "\n",
    "\n",
    "    #     def dfs(current): #一定按照left-node-right来、 已经给了Node的定义，天然带着left right的属性\n",
    "    #         if not current: #如果当前是空了，（走到左边最头上\n",
    "    #             return\n",
    "    #         dfs(current.left) #1. 继续走到左边头--左递归\n",
    "    #         if not self.prev: # 如果prev 没有东西  ，说明是head---1就是head，prev没东西\n",
    "    #             self.head = current\n",
    "    #         else: #2. 做双向链接动作--node第二步\n",
    "    #             self.prev.right = current \n",
    "    #             current.left = self.prev\n",
    "\n",
    "    #         self.prev = current #一定要先移动prev，要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "    #         dfs(current.right) #3. 继续向右看--右递归\n",
    "\n",
    "    #     dfs(root) #call\n",
    "\n",
    "    #     #最后还要头尾相连. 上面dfs走完后， self.prev其实是在末尾了\n",
    "    #     self.prev.right = self.head #末尾连接头\n",
    "    #     self.head.left = self.prev #头连接末尾\n",
    "\n",
    "    #     return self.head\n",
    "    # # -----_____----\n",
    "\n",
    "\n",
    "\n",
    "        # dfs, in order , 一定要左中右\n",
    "        # 要一个全局prev和head\n",
    "        # 首尾连接\n",
    "\n",
    "        # in order , dfs() 首尾相连，最后别忘了head prev相连\n",
    "        if not root:\n",
    "            return #?????\n",
    "\n",
    "        self.prev = None\n",
    "        self.head = None\n",
    "\n",
    "        def dfs(current):\n",
    "            if not current: #edge case走到头了\n",
    "                return #????\n",
    "\n",
    "            dfs(current.left)\n",
    "\n",
    "            #持续向左搜索，直到走到头，那么current就是head\n",
    "            if not self.prev:\n",
    "                self.head = current\n",
    "            else:#double link\n",
    "                self.prev.right = current\n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current\n",
    "        \n",
    "            dfs(current.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        self.prev.right = self.head\n",
    "        self.head.left = self.prev\n",
    "\n",
    "        return self.head\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # 方法1： 数组辅助\n",
    "        if root == None: return None\n",
    "        lst = []\n",
    "        def inOrder(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            inOrder(node.left)\n",
    "            lst.append(node)\n",
    "            inOrder(node.right)\n",
    "\n",
    "        inOrder(root)\n",
    "\n",
    "        n = len(lst)\n",
    "        for i in range(len(lst)):\n",
    "            lst[i].left = lst[(i-1)%n]\n",
    "            lst[i].right = lst[(i+1)%n]\n",
    "        return lst[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return\n",
    "        head=Node(-1,None,None)\n",
    "        prev=head\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            prev.right=root\n",
    "            root.left=prev\n",
    "            prev=prev.right\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        head.right.left=prev\n",
    "        prev.right=head.right\n",
    "        return head.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        node_arr = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            node_arr.append(root)\n",
    "            dfs(root.right)\n",
    "            return \n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        n = len(node_arr)\n",
    "        for i in range(n-1):\n",
    "            a1,a2 = node_arr[i],node_arr[i+1]\n",
    "            a1.right = a2 \n",
    "            a2.left = a1\n",
    "        a1,a2 = node_arr[-1],node_arr[0]\n",
    "        a1.right = a2\n",
    "        a2.left =a1\n",
    "        return node_arr[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root1: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "                root.left = self.pre\n",
    "            else:\n",
    "                self.head = root\n",
    "            self.pre = root\n",
    "            dfs(root.right)\n",
    "        if not root1: return\n",
    "        self.pre = None\n",
    "        dfs(root1)\n",
    "        self.pre.right = self.head\n",
    "        self.head.left = self.pre\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root: return \n",
    "        head = prev = Node(0)\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        prev.right = head.right\n",
    "        head.right.left = prev\n",
    "        \n",
    "        return head.right\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def change_to_List(root):\n",
    "            nonlocal root_last,head\n",
    "            if root==None:\n",
    "                return\n",
    "            change_to_List(root.left)\n",
    "        \n",
    "            root_last.right=root\n",
    "            if root_last!=head:\n",
    "                root.left=root_last\n",
    "            root_last=root\n",
    "\n",
    "            change_to_List(root.right)\n",
    "        \n",
    "        \n",
    "        if root==None:\n",
    "            return None\n",
    "        p=root\n",
    "        while p.right!=None:\n",
    "            p=p.right\n",
    "        head=Node(None)\n",
    "        root_last=head\n",
    "        change_to_List(root)\n",
    "\n",
    "        p.right=head.right\n",
    "        head.right.left=p\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        \n",
    "        # def travel(root):\n",
    "\n",
    "        #     # print(root.val)\n",
    "\n",
    "        #     right_max, left_min = None, None\n",
    "\n",
    "        #     if root.left:\n",
    "        #         left_max, left_min = travel(root.left)\n",
    "        #         root.left = left_max\n",
    "        #         left_max.right = root\n",
    "        #         # print('update left', root.left.val)\n",
    "        #     if root.right:\n",
    "        #         right_max, right_min = travel(root.right)\n",
    "        #         root.right = right_min\n",
    "        #         right_min.left = root\n",
    "        #         # print('update right', root.right.val)\n",
    "\n",
    "        #     if not right_max:\n",
    "        #         right_max = root\n",
    "        #     if not left_min:\n",
    "        #         left_min = root\n",
    "        #     # print('return', right_max.val, left_min.val)\n",
    "        #     return right_max, left_min\n",
    "        # if not root:\n",
    "        #     return None\n",
    "        # max_node, min_node = travel(root)\n",
    "        # # print('max', max_node.val, max_node.left.val)\n",
    "        # # print('min', min_node.val,min_node.right.val)\n",
    "        # max_node.right = min_node\n",
    "        # min_node.left = max_node\n",
    "        # # head = Node(0)\n",
    "        # # head.right = min_node\n",
    "        # return min_node\n",
    "\n",
    "        def travel(root):\n",
    "            if not root:\n",
    "                return None\n",
    "\n",
    "            travel(root.left)\n",
    "\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "                root.left = self.pre\n",
    "            else:\n",
    "                self.head = root\n",
    "\n",
    "            self.pre = root\n",
    "            travel(root.right)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        self.pre = None\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        travel(root)\n",
    "        self.pre.right = self.head\n",
    "        self.head.left = self.pre\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        prev = None\n",
    "        head = None\n",
    "        def in_order(node):\n",
    "            nonlocal prev, head\n",
    "            if not node:\n",
    "                return\n",
    "            in_order(node.left)\n",
    "            if not prev:\n",
    "                head = node\n",
    "            else:\n",
    "                prev.right = node\n",
    "                node.left = prev\n",
    "            prev = node\n",
    "            in_order(node.right)\n",
    "        in_order(root)\n",
    "        prev.right = head\n",
    "        head.left = prev\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        def in_order(node):\n",
    "            if not node:\n",
    "                return\n",
    "            in_order(node.left)\n",
    "            if not self.prev:\n",
    "                self.head = node\n",
    "            else:\n",
    "                self.prev.right = node\n",
    "                node.left = self.prev\n",
    "            self.prev = node\n",
    "            in_order(node.right)\n",
    "        self.prev = None\n",
    "        self.head = None\n",
    "        in_order(root)\n",
    "        self.prev.right = self.head\n",
    "        self.head.left = self.prev\n",
    "        return self.head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "\n",
    "        # 中序遍历的递归\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None,  right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        def dfs(node):\n",
    "            nonlocal last, first\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if last:\n",
    "                last.right = node\n",
    "                node.left = last\n",
    "            else:\n",
    "                first = node        \n",
    "            last = node\n",
    "            dfs(node.right)\n",
    "        \n",
    "        first, last = None, None\n",
    "        dfs(root)\n",
    "        last.right = first\n",
    "        first.left = last\n",
    "        return first\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left) # 递归左子树\n",
    "            if self.pre: # 修改节点引用\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: # 记录头节点\n",
    "                self.head = cur\n",
    "            self.pre = cur # 保存 cur\n",
    "            dfs(cur.right) # 递归右子树\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "\n",
    "        self.head = None \n",
    "        self.prev =None\n",
    "\n",
    "        # in order: left - node - right\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(current):\n",
    "            if not current: #stop\n",
    "                return  \n",
    "\n",
    "\n",
    "            dfs(current.left)#一路向左\n",
    "\n",
    "\n",
    "\n",
    "            #找到头节点。什么时候reach 了self\n",
    "\n",
    "            if not self.prev:\n",
    "                self.head = current\n",
    "            else:\n",
    "                #link \n",
    "                self.prev.right = current\n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current\n",
    "\n",
    "            dfs(current.right)\n",
    "\n",
    "            return self.head\n",
    "        \n",
    "        #首尾相连\n",
    "        dfs(root)\n",
    "        self.prev.right = self.head\n",
    "        self.head.left = self.prev\n",
    "\n",
    "        return self.head\n",
    "            \n",
    "# 时间和空间复杂度\n",
    "# 时间复杂度：O(N)，其中 N 是树中的节点数。需要遍历所有节点。\n",
    "# 空间复杂度：O(H)，其中 H 是树的高度。这对应于递归栈的深度。\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def inorder(root):\n",
    "            nonlocal first, prev\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            if not first:\n",
    "                first = root\n",
    "            if prev:\n",
    "                prev.right, root.left = root, prev\n",
    "            prev = root\n",
    "            inorder(root.right)\n",
    "            \n",
    "        first, prev = None, None\n",
    "        inorder(root)\n",
    "        if first:\n",
    "            first.left, prev.right = prev, first\n",
    "        return first\n",
    "        \n",
    "\n",
    "\n",
    "    # def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "    #     def helper(root):\n",
    "    #         if not root: return None, None\n",
    "    #         print(root.val)\n",
    "    #         if not root.left and not root.right: \n",
    "    #             root.left, root.right = root, root # 1WA\n",
    "    #             return root, root\n",
    "    #         left_head, left_tail = helper(root.left)\n",
    "    #         right_head, right_tail = helper(root.right)\n",
    "    #         if not root.left:\n",
    "    #             root.right, root.left = right_head, right_tail\n",
    "    #             right_head.left, right_tail.right = root, root\n",
    "    #             return root, right_tail\n",
    "    #         if not root.right:\n",
    "    #             root.left, root.right = left_tail, left_head\n",
    "    #             left_tail.right, left_head.left = root, root\n",
    "    #             return left_head, root\n",
    "    #         root.left, root.right = left_tail, right_head\n",
    "    #         left_tail.right, right_head.left, left_head.left, right_tail.right = root, root, right_tail, left_head # 2WA: forgot the last two cases\n",
    "    #         return left_head, right_tail\n",
    "\n",
    "    #     return helper(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:return \n",
    "        # 当一个中间节点\n",
    "        head = Node(-1, None, None)\n",
    "        # 记录为先前节点,找到下一个节点才能串起来\n",
    "        prev = head\n",
    "\n",
    "        # 中序遍历的递归\n",
    "        def inorder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev\n",
    "            prev = prev.right\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        # 将head 删掉   \n",
    "        head.right.left = prev\n",
    "        prev.right = head.right\n",
    "        return head.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # inorder traverse -> list -> double linked list\n",
    "        if not root: return\n",
    "        \n",
    "        dummy = Node(-1)\n",
    "        pre = dummy\n",
    "        \n",
    "        def inorderTraverse(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            inorderTraverse(root.left)\n",
    "\n",
    "            pre.right = root\n",
    "            root.left = pre\n",
    "            pre = pre.right \n",
    "            \n",
    "            inorderTraverse(root.right)\n",
    "        \n",
    "        inorderTraverse(root)\n",
    "        # remove dummy node, break bi-direction links\n",
    "        # pre(tail) = dummy = dummy.right\n",
    "        dummy.right.left = pre\n",
    "        pre.right = dummy.right\n",
    "         \n",
    "        return pre.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        \n",
    "        # 递归写法\n",
    "        if root is None:\n",
    "            return None\n",
    "            \n",
    "        dummy = Node(0)\n",
    "        prev = dummy  # 设置一个虚头节点\n",
    "        # 中序遍历\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            nonlocal prev\n",
    "            prev.right = node\n",
    "            node.left = prev\n",
    "            prev = node\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        prev.right = dummy.right\n",
    "        dummy.right.left = prev\n",
    "        return dummy.right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return\n",
    "        head = Node(-1)\n",
    "        prev = head\n",
    "\n",
    "        def middlerOrder(root):\n",
    "            nonlocal prev\n",
    "            if not root:\n",
    "                return root\n",
    "            middlerOrder(root.left)\n",
    "            prev.right = root\n",
    "            root.left = prev \n",
    "            prev = prev.right\n",
    "            middlerOrder(root.right)\n",
    "\n",
    "        middlerOrder(root)\n",
    "        # 链接首尾节点\n",
    "        head.right.left = prev \n",
    "        prev.right = head.right\n",
    "        return head.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def d(c):\n",
    "            if not c: return\n",
    "            d(c.left)\n",
    "            if self.pre:\n",
    "                self.pre.right, c.left = c, self.pre\n",
    "            else:\n",
    "                self.head = c\n",
    "            self.pre = c\n",
    "            d(c.right)\n",
    "\n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        d(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        first, last = None, None\n",
    "        def dfs(node):\n",
    "            nonlocal first, last\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            dfs(node.left)\n",
    "\n",
    "            if last:\n",
    "                last.right = node\n",
    "                node.left = last\n",
    "            else:\n",
    "                # record the min node\n",
    "                first = node\n",
    "            last = node\n",
    "\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        first.left = last\n",
    "        last.right = first\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        head = Node(-1)\n",
    "        cur = head # 存放当前链表末尾的元素\n",
    "        def traverse(node):\n",
    "            # 要确保当前这个节点被摘出，和整棵树完全断开 - 中序遍历\n",
    "            if not node:\n",
    "                return\n",
    "            temp = node.right\n",
    "            traverse(node.left)\n",
    "            # 摘掉node，接在cur后面\n",
    "            nonlocal cur\n",
    "            cur.right = node\n",
    "            node.left = cur\n",
    "            node.right = None\n",
    "            cur = cur.right\n",
    "\n",
    "            traverse(temp)\n",
    "        traverse(root)\n",
    "        cur.right = head.right\n",
    "        if head.right:\n",
    "            head.right.left = cur\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left)\n",
    "# //pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点\n",
    "            if not self.pre: \n",
    "                self.head = cur\n",
    "            else:\n",
    "                self.pre.right = cur\n",
    "                cur.left = self.pre\n",
    "            self.pre = cur # pre指向当前的cur\n",
    "            dfs(cur.right) \n",
    "            \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        # 进行头尾链接\n",
    "        self.pre.right = self.head\n",
    "        self.head.left = self.pre\n",
    "        return self.head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        data = []\n",
    "        if root == None:\n",
    "            return root\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            data.append(root)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        n = len(data)\n",
    "        data[0].left = data[-1]\n",
    "        data[-1].right = data[0]\n",
    "        for i in range(n):\n",
    "            if i != n -1:\n",
    "                data[i].right = data[i+1]\n",
    "            if i != 0:\n",
    "                data[i].left = data[i-1]\n",
    "        return data[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if root is None:\n",
    "            return root\n",
    "        \n",
    "        first = None\n",
    "        last = None\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            nonlocal last, first\n",
    "            dfs(node.left)\n",
    "\n",
    "            if last is None:\n",
    "                # reach the first element in the in-order traversal sequence\n",
    "                last = node\n",
    "                first = node\n",
    "            else:\n",
    "                node.left = last\n",
    "                last.right = node\n",
    "                last = node\n",
    "\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        last.right = first\n",
    "        first.left = last\n",
    "\n",
    "        return first\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        self.first, self.last = None, None\n",
    "        def helper(node):\n",
    "            if node:\n",
    "                helper(node.left)\n",
    "                if self.last:\n",
    "                    self.last.right = node\n",
    "                    node.left = self.last\n",
    "                else:\n",
    "                    self.first = node\n",
    "                self.last = node\n",
    "                helper(node.right)\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        helper(root)\n",
    "        self.last.right = self.first\n",
    "        self.first.left = self.last\n",
    "        return self.first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "        if root==None:\n",
    "            return root\n",
    "        line=[]\n",
    "\n",
    "        def method(node):\n",
    "            nonlocal line\n",
    "            if not node:\n",
    "                return \n",
    "            else:\n",
    "                method(node.left)\n",
    "                line.append(node)\n",
    "                method(node.right)\n",
    "\n",
    "        method(root)\n",
    "\n",
    "        for idt in range(1,len(line)):\n",
    "            q_node=line[idt-1]\n",
    "            h_node=line[idt]\n",
    "            q_node.right=h_node\n",
    "            h_node.left=q_node\n",
    "\n",
    "        q_node=line[0]\n",
    "        h_node=line[-1]\n",
    "        q_node.left=h_node\n",
    "        h_node.right=q_node\n",
    "\n",
    "        return line[0]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for a Node.\r\n",
    "class Node:\r\n",
    "    def __init__(self, val, left=None, right=None):\r\n",
    "        self.val = val\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\"\"\"\r\n",
    "class Solution:\r\n",
    "    # 分治，递归\r\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\r\n",
    "        if not root: return\r\n",
    "        left = self.treeToDoublyList(root.left)\r\n",
    "        right = self.treeToDoublyList(root.right)\r\n",
    "        root.left = root\r\n",
    "        root.right = root\r\n",
    "        return self.connect(self.connect(left, root), right)\r\n",
    "\r\n",
    "    def connect(self, node1, node2):\r\n",
    "        if not (node1 and node2):\r\n",
    "            return node1 or node2\r\n",
    "        tail1, tail2 = node1.left, node2.left\r\n",
    "        tail1.right = node2\r\n",
    "        node2.left = tail1\r\n",
    "        tail2.right = node1\r\n",
    "        node1.left = tail2\r\n",
    "        return node1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if root == None:\n",
    "            return root\n",
    "        self.head = None\n",
    "        self.pre = None\n",
    "        self.mid_order(root)\n",
    "\n",
    "\n",
    "        self.head.left,  self.pre.right = self.pre, self.head\n",
    "        # print(self.head.val)\n",
    "        return self.head\n",
    "\n",
    "\n",
    "    def mid_order(self,root):\n",
    "        if root == None:\n",
    "            return \n",
    "        self.mid_order(root.left)\n",
    "        if self.pre == None:\n",
    "            self.head = root\n",
    "        else:\n",
    "            self.pre.right,root.left = root, self.pre\n",
    "        self.pre = root\n",
    "        self.mid_order(root.right)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return\n",
    "        self.pre = None\n",
    "        self.head = None\n",
    "        self.inorder(root)\n",
    "        self.head.left = self.pre\n",
    "        self.pre.right = self.head\n",
    "        return self.head\n",
    "        \n",
    "    def inorder(self, node):\n",
    "        if node.left:\n",
    "            self.inorder(node.left)\n",
    "        # 第一次执行到这里的时候是最小值\n",
    "        if not self.head:\n",
    "            self.head = node\n",
    "        if self.pre:\n",
    "            self.pre.right = node\n",
    "            node.left = self.pre\n",
    "        self.pre = node\n",
    "        if node.right:\n",
    "            self.inorder(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(cur):\n",
    "            if not cur: return\n",
    "            dfs(cur.left) # 递归左子树\n",
    "            if self.pre: # 修改节点引用\n",
    "                self.pre.right, cur.left = cur, self.pre\n",
    "            else: # 记录头节点\n",
    "                self.head = cur\n",
    "            self.pre = cur # 保存 cur\n",
    "            dfs(cur.right) # 递归右子树\n",
    "        \n",
    "        if not root: return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left, self.pre.right = self.pre, self.head\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root: return \n",
    "\n",
    "        first = None\n",
    "        last = None\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal first, last\n",
    "            if not node: return \n",
    "\n",
    "            dfs(node.left)\n",
    "            if last:\n",
    "                last.right = node\n",
    "                node.left = last\n",
    "            else:\n",
    "                first = node\n",
    "            \n",
    "            last = node\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        first.left = last\n",
    "        last.right = first\n",
    "\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':   \n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "            dfs(cur.left)\n",
    "            if self.pre:\n",
    "                self.pre.right,cur.left = cur,self.pre#进行双向链表\n",
    "            else:#pre一开始没数据,所以是null\n",
    "                self.head = cur\n",
    "            self.pre = cur\n",
    "            dfs(cur.right)\n",
    "        if not root:\n",
    "            return\n",
    "        self.pre = None\n",
    "        dfs(root)\n",
    "        self.head.left,self.pre.right = self.pre,self.head\n",
    "        return self.head\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def inorderTraverse(cur):\n",
    "            if not cur: return \n",
    "            inorderTraverse(cur.left)\n",
    "            if not self.pre:\n",
    "                self.head = cur\n",
    "            else:\n",
    "                self.pre.right = cur \n",
    "                cur.left = self.pre\n",
    "            self.pre = cur \n",
    "            inorderTraverse(cur.right)\n",
    "        if not root: return \n",
    "        self.pre = None\n",
    "        inorderTraverse(root)\n",
    "        self.head.left = self.pre \n",
    "        self.pre.right = self.head\n",
    "        return self.head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root: return\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node: return None, None\n",
    "\n",
    "            lmin,lmax = dfs(node.left)\n",
    "\n",
    "            #print(node.val, lmin,lmax)\n",
    "            if lmax:\n",
    "                lmax.right = node           \n",
    "                node.left = lmax\n",
    "\n",
    "            rmin, rmax = dfs(node.right)\n",
    "\n",
    "            \n",
    "            if rmin:\n",
    "                node.right = rmin\n",
    "                rmin.left = node\n",
    "\n",
    "            lmin = lmin if lmin else node\n",
    "            rmax = rmax if rmax else node\n",
    "            \n",
    "            return lmin, rmax\n",
    "\n",
    "                \n",
    "        left, right = dfs(root)\n",
    "        left.left = right\n",
    "        right.right = left\n",
    "        return left\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        def dfs(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                root.left = root\n",
    "                root.right = root\n",
    "                return root, root\n",
    "\n",
    "\n",
    "            if root.left is None:\n",
    "                # root [c, d]\n",
    "                c, d = dfs(root.right)\n",
    "                root.right = c\n",
    "                c.left = root\n",
    "                root.left = d\n",
    "                d.right = root\n",
    "                return (root, d)\n",
    "            if root.right is None:\n",
    "                # [a,b] root\n",
    "                a, b = dfs(root.left)\n",
    "                a.left = root\n",
    "                b.right = root\n",
    "                root.left = b\n",
    "                root.right = a\n",
    "                return (a, root)\n",
    "\n",
    "            # [a,b] root [c,d]\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "\n",
    "            root.left = b\n",
    "            b.right = root\n",
    "            root.right = c\n",
    "            c.left = root\n",
    "            d.right = a\n",
    "            a.left = d\n",
    "            return (a, d)\n",
    "\n",
    "        res, _ = dfs(root)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        def _inOrder(root):\n",
    "            if root.left:\n",
    "                _inOrder(root.left)\n",
    "            \n",
    "            if self.prev:\n",
    "                self.prev.right = root\n",
    "                root.left = self.prev\n",
    "            else:\n",
    "                self.head = root\n",
    "            self.prev = root\n",
    "            if root.right:\n",
    "                _inOrder(root.right)\n",
    "\n",
    "        self.prev = None\n",
    "        self.head = None\n",
    "        _inOrder(root)\n",
    "        self.head.left = self.prev\n",
    "        self.prev.right = self.head\n",
    "\n",
    "        return self.head\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "'''\n",
    "in-Order\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def change_to_List(root):\n",
    "            nonlocal root_last,head\n",
    "            if root==None:\n",
    "                return\n",
    "            change_to_List(root.left)\n",
    "        \n",
    "            root_last.right=root\n",
    "            if root_last!=head:\n",
    "                root.left=root_last\n",
    "            root_last=root\n",
    "\n",
    "            change_to_List(root.right)\n",
    "        \n",
    "        \n",
    "        if root==None:\n",
    "            return None\n",
    "        p=root\n",
    "        while p.right!=None:\n",
    "            p=p.right\n",
    "        head=Node(None)\n",
    "        root_last=head\n",
    "        change_to_List(root)\n",
    "\n",
    "        p.right=head.right\n",
    "        head.right.left=p\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "\n",
    "        self.head = None \n",
    "        self.prev =None\n",
    "\n",
    "        # in order: left - node - right\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(current):\n",
    "            if not current: #stop\n",
    "                return  \n",
    "\n",
    "\n",
    "            dfs(current.left)#一路向左\n",
    "\n",
    "\n",
    "\n",
    "            #找到头节点。什么时候reach 了self\n",
    "\n",
    "            if not self.prev:\n",
    "                self.head = current\n",
    "            else:\n",
    "                #link \n",
    "                self.prev.right = current\n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current\n",
    "\n",
    "            dfs(current.right)\n",
    "\n",
    "            return self.head\n",
    "        \n",
    "        #首尾相连\n",
    "        dfs(root)\n",
    "        self.prev.right = self.head\n",
    "        self.head.left = self.prev\n",
    "\n",
    "        return self.head\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        def linkNode(root):\n",
    "            L, R = False, False\n",
    "            if root.left:\n",
    "                L = True\n",
    "                ll, lr = linkNode(root.left)\n",
    "            if root.right:\n",
    "                R = True\n",
    "                rl, rr = linkNode(root.right)\n",
    "            \n",
    "            if L:\n",
    "                root.left = lr\n",
    "                lr.right = root\n",
    "            if R:\n",
    "                root.right = rl\n",
    "                rl.left = root\n",
    "            \n",
    "            if L and R:\n",
    "                ll.left = rr\n",
    "                rr.right = ll\n",
    "                return ll, rr\n",
    "            elif L:\n",
    "                ll.left = root\n",
    "                root.right = ll\n",
    "                return ll, root\n",
    "            elif R:\n",
    "                root.left = rr\n",
    "                rr.right = root\n",
    "                return root, rr\n",
    "            else:\n",
    "                root.left = root\n",
    "                root.right = root \n",
    "                return root, root\n",
    "\n",
    "        left, right = linkNode(root)\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Divide and conquer solution is not easy to implement.\n",
    "# The inorder recursive traversal solution is pretty concise.\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def inorder(root):\n",
    "            nonlocal first, prev\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            if not first:\n",
    "                first = root\n",
    "            if prev:\n",
    "                prev.right, root.left = root, prev\n",
    "            prev = root\n",
    "            inorder(root.right)\n",
    "            \n",
    "        first, prev = None, None\n",
    "        inorder(root)\n",
    "        if first:\n",
    "            first.left, prev.right = prev, first\n",
    "        return first\n",
    "        \n",
    "\n",
    "\n",
    "    # def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "    #     def helper(root):\n",
    "    #         if not root: return None, None\n",
    "    #         print(root.val)\n",
    "    #         if not root.left and not root.right: \n",
    "    #             root.left, root.right = root, root # 1WA\n",
    "    #             return root, root\n",
    "    #         left_head, left_tail = helper(root.left)\n",
    "    #         right_head, right_tail = helper(root.right)\n",
    "    #         if not root.left:\n",
    "    #             root.right, root.left = right_head, right_tail\n",
    "    #             right_head.left, right_tail.right = root, root\n",
    "    #             return root, right_tail\n",
    "    #         if not root.right:\n",
    "    #             root.left, root.right = left_tail, left_head\n",
    "    #             left_tail.right, left_head.left = root, root\n",
    "    #             return left_head, root\n",
    "    #         root.left, root.right = left_tail, right_head\n",
    "    #         left_tail.right, right_head.left, left_head.left, right_tail.right = root, root, right_tail, left_head # 2WA: forgot the last two cases\n",
    "    #         return left_head, right_tail\n",
    "\n",
    "    #     return helper(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # https://www.youtube.com/watch?v=H5zop8o-HG4&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3\n",
    "\n",
    "        #结合linked list + bst\n",
    "\n",
    "        #两种方法， 递归+  iterative\n",
    "\n",
    "        #  dfs 三种遍历： \n",
    "        #  in order中序： left - node -right\n",
    "        #  preorder 前序： node -left -right\n",
    "        #  post order: left - right - node\n",
    "\n",
    "        #由于给你的是bst， 左小右大，所以用中序遍历。拿出来一定是排序好的节点：left-node-right\n",
    "\n",
    "        #另外是double linked list,需要prev。 利用in order遍历到bst的最左下（最小值），\n",
    "        # 1. base case ： if not current: return None\n",
    "\n",
    "        # 2. 对当前节点的left 开始递归\n",
    "        # 如果当前节点的prev是空的，那说明走到左下角头（第一次递归到头一定是左下角）那他就是head \n",
    "        # 如果此时prev是空，那他就是head嘛\n",
    "        # 如果prev不是空，那就link： prev-><-current\n",
    "        # 然后就把prev变成当前点:继续向右走（当继续下一个点的时候，当前点就会是下一个点的prev）--prev先走--要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "        # 然后对当前节点右侧调用递归\n",
    "\n",
    "        #遍历完之后，表示doulbe linked list 完成\n",
    "\n",
    "        #主要要变成circular， 也就是头尾也相连\n",
    "        #最后return head\n",
    "\n",
    "\n",
    "        #先移动prev，在移动current\n",
    "\n",
    "\n",
    "####1 recursi\n",
    "\n",
    "    #     if not root: #首先在外面也需要一个，如果根节点是空的，直接啥也不用干\n",
    "    #         return\n",
    "\n",
    "\n",
    "    #     #这俩都是空的一开始\n",
    "    #     self.head = None # global variable\n",
    "    #     self.prev = None #是node哦，node有val， left，right\n",
    "\n",
    "\n",
    "\n",
    "    #     def dfs(current): #一定按照left-node-right来、 已经给了Node的定义，天然带着left right的属性\n",
    "    #         if not current: #如果当前是空了，（走到左边最头上\n",
    "    #             return\n",
    "    #         dfs(current.left) #1. 继续走到左边头--左递归\n",
    "    #         if not self.prev: # 如果prev 没有东西  ，说明是head---1就是head，prev没东西\n",
    "    #             self.head = current\n",
    "    #         else: #2. 做双向链接动作--node第二步\n",
    "    #             self.prev.right = current \n",
    "    #             current.left = self.prev\n",
    "\n",
    "    #         self.prev = current #一定要先移动prev，要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "    #         dfs(current.right) #3. 继续向右看--右递归\n",
    "\n",
    "    #     dfs(root) #call\n",
    "\n",
    "    #     #最后还要头尾相连. 上面dfs走完后， self.prev其实是在末尾了\n",
    "    #     self.prev.right = self.head #末尾连接头\n",
    "    #     self.head.left = self.prev #头连接末尾\n",
    "\n",
    "    #     return self.head\n",
    "    # # -----_____----\n",
    "\n",
    "\n",
    "\n",
    "        # dfs, in order , 一定要左中右\n",
    "        # 要一个全局prev和head\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        self.head =None\n",
    "        self.prev = None#用于链接double list\n",
    "        def dfs(current):\n",
    "            if not current:\n",
    "                return\n",
    "            dfs(current.left) #持续向左\n",
    "\n",
    "            if not self.prev: #一直向左，如果找到null，那就是头，最左下角\n",
    "                self.head = current \n",
    "            else: #不然就要给list添加link\n",
    "                self.prev.right = current\n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current\n",
    "            dfs(current.right)\n",
    "    \n",
    "        dfs(root)\n",
    "        #最后首尾连接\n",
    "        self.prev.right = self.head\n",
    "        self.head.left = self.prev\n",
    "        return self.head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:    return None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            \n",
    "            Lstart, Lend = dfs(root.left)\n",
    "            Rstart, Rend = dfs(root.right)\n",
    "            ansL = ansR = root\n",
    "            if Lstart:\n",
    "                root.left, Lend.right = Lend, root\n",
    "                ansL = Lstart\n",
    "            if Rstart:\n",
    "                root.right, Rstart.left = Rstart, root\n",
    "                ansR = Rend\n",
    "            return ansL, ansR\n",
    "        \n",
    "        ansL, ansR = dfs(root)\n",
    "        ansL.left, ansR.right = ansR, ansL\n",
    "        return ansL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def helper(root):\n",
    "            if not root: return None, None\n",
    "            print(root.val)\n",
    "            if not root.left and not root.right: \n",
    "                root.left, root.right = root, root # 1WA\n",
    "                return root, root\n",
    "            if not root.left:\n",
    "                right_head, right_tail = helper(root.right)\n",
    "                root.right, root.left = right_head, right_tail\n",
    "                right_head.left, right_tail.right = root, root\n",
    "                return root, right_tail\n",
    "            if not root.right:\n",
    "                left_head, left_tail = helper(root.left)\n",
    "                root.left, root.right = left_tail, left_head\n",
    "                left_tail.right, left_head.left = root, root\n",
    "                return left_head, root\n",
    "            left_head, left_tail = helper(root.left)\n",
    "            right_head, right_tail = helper(root.right)\n",
    "            root.left, root.right = left_tail, right_head\n",
    "            left_tail.right, right_head.left, left_head.left, right_tail.right = root, root, right_tail, left_head\n",
    "            return left_head, right_tail\n",
    "\n",
    "        return helper(root)[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # https://www.youtube.com/watch?v=H5zop8o-HG4&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3\n",
    "\n",
    "        #结合linked list + bst\n",
    "\n",
    "        #两种方法， 递归+  iterative\n",
    "\n",
    "        #  dfs 三种遍历： \n",
    "        #  in order中序： left - node -right\n",
    "        #  preorder 前序： node -left -right\n",
    "        #  post order: left - right - node\n",
    "\n",
    "        #由于给你的是bst， 左小右大，所以用中序遍历。拿出来一定是排序好的节点：left-node-right\n",
    "\n",
    "        #另外是double linked list,需要prev。 利用in order遍历到bst的最左下（最小值），\n",
    "        # 1. base case ： if not current: return None\n",
    "\n",
    "        # 2. 对当前节点的left 开始递归\n",
    "        # 如果当前节点的prev是空的，那说明走到左下角头（第一次递归到头一定是左下角）那他就是head \n",
    "        # 如果此时prev是空，那他就是head嘛\n",
    "        # 如果prev不是空，那就link： prev-><-current\n",
    "        # 然后就把prev变成当前点:继续向右走（当继续下一个点的时候，当前点就会是下一个点的prev）--prev先走--要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "        # 然后对当前节点右侧调用递归\n",
    "\n",
    "        #遍历完之后，表示doulbe linked list 完成\n",
    "\n",
    "        #主要要变成circular， 也就是头尾也相连\n",
    "        #最后return head\n",
    "\n",
    "\n",
    "        #先移动prev，在移动current\n",
    "\n",
    "\n",
    "####1 recursi\n",
    "\n",
    "        if not root: #首先在外面也需要一个，如果根节点是空的，直接啥也不用干\n",
    "            return\n",
    "\n",
    "\n",
    "        #这俩都是空的一开始\n",
    "        self.head = None # global variable\n",
    "        self.prev = None #是node哦，node有val， left，right\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(current): #一定按照left-node-right来\n",
    "            if not current: #如果当前是空了，（走到左边最头上\n",
    "                return\n",
    "            dfs(current.left) #1. 继续走到左边头--左递归\n",
    "            if not self.prev: # 如果prev 没有东西  ，说明是head---1就是head，prev没东西\n",
    "                self.head = current\n",
    "            else: #2. 做双向链接动作--node第二步\n",
    "                self.prev.right = current \n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current #一定要先移动prev，要在进入右子树之前设置好 self.prev。\n",
    "\n",
    "            dfs(current.right) #3. 继续向右看--右递归\n",
    "\n",
    "        dfs(root) #call\n",
    "\n",
    "        #最后还要头尾相连. 上面dfs走完后， self.prev其实是在末尾了\n",
    "        self.prev.right = self.head #末尾连接头\n",
    "        self.head.left = self.prev #头连接末尾\n",
    "\n",
    "        return self.head\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        self.first = None\n",
    "        self.last = None\n",
    "        def dfs(node):\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            dfs(node.left)\n",
    "\n",
    "            if self.last:\n",
    "                self.last.right = node\n",
    "                node.left = self.last\n",
    "            else:\n",
    "                self.first = node\n",
    "    \n",
    "            self.last = node\n",
    "\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        \n",
    "        self.first.left = self.last\n",
    "        self.last.right = self.first\n",
    "\n",
    "        return self.first\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if root is None:\n",
    "            return None\n",
    "        inlist = self.inorder(root)\n",
    "        head = inlist[0]\n",
    "        for i in range(len(inlist)):\n",
    "            if i<len(inlist)-1:\n",
    "                inlist[i].left = inlist[i-1]\n",
    "                inlist[i].right = inlist[i+1]\n",
    "            else:\n",
    "                inlist[i].left = inlist[i-1]\n",
    "                inlist[i].right = inlist[0]\n",
    "        return head\n",
    "\n",
    "    def inorder(self, node):\n",
    "        if node is None:\n",
    "            return []\n",
    "        return self.inorder(node.left)+[node]+self.inorder(node.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, node):\n",
    "        left_start = None\n",
    "        left_end = None\n",
    "        right_start = None\n",
    "        right_end = None\n",
    "        if node.left:\n",
    "            left_start, left_end = self.dfs(node.left)\n",
    "        if node.right:\n",
    "            right_start, right_end = self.dfs(node.right)\n",
    "        if left_end:\n",
    "            node.left = left_end\n",
    "            left_end.right = node\n",
    "        if right_start:\n",
    "            node.right = right_start\n",
    "            right_start.left = node\n",
    "        start = None\n",
    "        if left_start:\n",
    "            start = left_start\n",
    "        else:\n",
    "            start = node\n",
    "        end = None\n",
    "        if right_end:\n",
    "            end = right_end\n",
    "        else:\n",
    "            end = node\n",
    "        return start, end\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        start, end = self.dfs(root)\n",
    "        \n",
    "        start.left = end\n",
    "        end.right = start\n",
    "        return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def inorderTraverse(cur):\n",
    "            if not cur: return \n",
    "            inorderTraverse(cur.left)\n",
    "            if not self.pre:\n",
    "                self.head = cur\n",
    "            else:\n",
    "                self.pre.right = cur \n",
    "                cur.left = self.pre\n",
    "            self.pre = cur \n",
    "            inorderTraverse(cur.right)\n",
    "        if not root: return \n",
    "        self.pre = None\n",
    "        inorderTraverse(root)\n",
    "        self.head.left = self.pre \n",
    "        self.pre.right = self.head\n",
    "        return self.head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None\n",
    "        if not root.left and not root.right:\n",
    "            root.right=root\n",
    "            root.left=root\n",
    "            return root\n",
    "        if not root.right and root.left:\n",
    "            tleft=self.treeToDoublyList(root.left)\n",
    "            cur1=tleft.left\n",
    "            cur1.right=root\n",
    "            root.right=tleft\n",
    "            tleft.left=root\n",
    "            root.left=cur1\n",
    "            return tleft\n",
    "        if not root.left and root.right:\n",
    "            tright=self.treeToDoublyList(root.right)\n",
    "            cur1=tright.left\n",
    "            root.right=tright\n",
    "            tright.left=root\n",
    "            cur1.right=root\n",
    "            root.left=cur1\n",
    "            return root\n",
    "\n",
    "        \n",
    "        tleft=self.treeToDoublyList(root.left)\n",
    "        tright=self.treeToDoublyList(root.right)\n",
    "        cur1=tleft.left\n",
    "        cur2=tright.left\n",
    "        cur1.right=root\n",
    "        root.left=cur1\n",
    "        root.right=tright\n",
    "        tright.left=root\n",
    "        tleft.left=cur2\n",
    "        cur2.right=tleft\n",
    "        return tleft\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        # https://www.youtube.com/watch?v=H5zop8o-HG4&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3\n",
    "\n",
    "        #结合linked list + bst\n",
    "\n",
    "        #两种方法， 递归+  iterative\n",
    "\n",
    "        #  dfs 三种遍历： \n",
    "        #  in order中序： left - node -right\n",
    "        #  preorder 前序： node -left -right\n",
    "        #  post order: left - right - node\n",
    "\n",
    "        #由于给你的是bst， 左小右大，所以用中序遍历。拿出来一定是排序好的节点：left-node-right\n",
    "\n",
    "        #另外是double linked list,需要prev。 利用in order遍历到bst的最左下（最小值），\n",
    "        # 1. base case ： if not current: return None\n",
    "\n",
    "        # 2. 对当前节点的left 开始递归\n",
    "        # 如果当前节点的prev是空的，那说明走到左下角头（第一次递归到头一定是左下角）那他就是head \n",
    "        # 如果此时prev是空，那他就是head嘛\n",
    "        # 如果prev不是空，那就link： prev-><-current\n",
    "        # 然后就把prev变成当前点:继续向右走（当继续下一个点的时候，当前点就会是下一个点的prev）--prev先走\n",
    "        # 然后对当前节点右侧调用递归\n",
    "\n",
    "        #遍历完之后，表示doulbe linked list 完成\n",
    "\n",
    "        #主要要变成circular， 也就是头尾也相连\n",
    "        #最后return head\n",
    "\n",
    "\n",
    "        #先移动prev，在移动current\n",
    "\n",
    "\n",
    "####1 recursi\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        self.head = None # global variable\n",
    "        self.prev = None #是node哦，node有val， left，right\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(current):\n",
    "            if not current: #如果当前是空了，（走到左边最头上\n",
    "                return\n",
    "            dfs(current.left) #继续走到左边头--左递归\n",
    "            if not self.prev: # 如果prev 没有东西  ，说明是head---1就是head，prev没东西\n",
    "                self.head = current\n",
    "            else: #做双向链接动作\n",
    "                self.prev.right = current \n",
    "                current.left = self.prev\n",
    "\n",
    "            self.prev = current #先移动prev\n",
    "\n",
    "            dfs(current.right) #继续向右看--右递归\n",
    "\n",
    "        dfs(root) #call\n",
    "\n",
    "        #最后还要头尾相连. 上面dfs走完后， self.prev其实是在末尾了\n",
    "        self.prev.right = self.head #末尾连接头\n",
    "        self.head.left = self.prev #头连接末尾\n",
    "\n",
    "        return self.head\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node. \n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "'''\n",
    "\n",
    "params: current node\n",
    "return: the node with max value\n",
    "todo: flatten the tree\n",
    "\n",
    "1. when meet the leaf, return node, node\n",
    "2. For node 2, it has left and right nodes and both are doubly-linked list, left_tail and right_tail\n",
    "    node.left  = left_tail\n",
    "    left_tail.right = node\n",
    "    node.right = right_head\n",
    "    right_head.left = node\n",
    "    return left_head, right_tail\n",
    "\n",
    "    how to find the head of a subtree?\n",
    "    1. Loop the doubly-linked list and find the head\n",
    "    *2. Return both head and tail\n",
    "    3. If it's circular, head is the next of tail; for subtree\n",
    "    4. Pass the current node to head\n",
    "\n",
    "3. For node that has only left and no right:\n",
    "    node.left = left_tail\n",
    "    left_tail.right = node\n",
    "    return left_head, node\n",
    "4. For node that has only right and no left:\n",
    "    node.right = right_head\n",
    "    right_head.left = node\n",
    "    return node, right_tail\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''\n",
    "To pass the variable to recursion:\n",
    "\n",
    "1. For current node, it knows who is it's parent \n",
    "2. Then it try to get it's left_head and right_tail \n",
    "\n",
    "    1. connect node with parent before return node when meet leaf\n",
    "\n",
    "    2. if it has both left_head and right_tail:\n",
    "        if parent node value > right_tail value:\n",
    "            parent.left = right_tail\n",
    "            right_tail.right = parent\n",
    "            return right_tail\n",
    "        if parent node value < left_head value:\n",
    "            parent.right = left_head\n",
    "            left_head.left = parent\n",
    "            return left_head\n",
    "\n",
    "    3. if it has only left_head:\n",
    "        if parent node value < left_head value:\n",
    "            parent.right = left_head\n",
    "            left_head.left = parent\n",
    "            return node\n",
    "        else:\n",
    "            parent.right = node\n",
    "            node.left = parent\n",
    "            return left_head \n",
    "\n",
    "    4. if it had only right_tail:\n",
    "        if parent node value > right_tail value:\n",
    "            parent.left = right_tail\n",
    "            right_tail.right = parent\n",
    "            return node \n",
    "        else:\n",
    "            parent.left = node\n",
    "            node.right = parent\n",
    "            return right_tail \n",
    "        \n",
    "    5. if don't have both:\n",
    "        node.right = node\n",
    "        node.left = node\n",
    "'''\n",
    "'''\n",
    "pass pre_node, return tail\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    params: node (current position), next (next node of the largest node of current subtree)\n",
    "    return: node (head)\n",
    "    todo: \n",
    "\n",
    "    1. for node 10:\n",
    "        - node 10, left 5 and right 15\n",
    "        - left head 4, right head 14\n",
    "    2. for node 3: \n",
    "        - pass current node to left node\n",
    "        - pass next to right \n",
    "        - link to right head\n",
    "        node.right = right_head \n",
    "        right_head.left = node\n",
    "        return left_head\n",
    "    3. for node 5:\n",
    "        - pass current node to left node\n",
    "        - pass next to right \n",
    "        node.right = right_head \n",
    "        right_head.left = node\n",
    "        return left_head\n",
    "    4. for leaf node:\n",
    "        node.right = next \n",
    "        next.left = node\n",
    "        return node\n",
    "\n",
    "    5. if left_head and not right_head:\n",
    "        node.right = next\n",
    "        next.left = node\n",
    "        return left_head\n",
    "\n",
    "    6. if not left_head and right_head:\n",
    "        node.right = right_head\n",
    "        right_head.left = node\n",
    "        return node\n",
    "\n",
    "    create a dummy node, dummy_node.left = node 10\n",
    "\n",
    "    '''\n",
    "    def helper(self, node, next_node):\n",
    "        if not node:\n",
    "            return None\n",
    "\n",
    "        if not node.left and not node.right:\n",
    "            node.right = next_node\n",
    "            next_node.left = node\n",
    "            return node\n",
    "\n",
    "        left_head = self.helper(node.left, node)\n",
    "        right_head = self.helper(node.right, next_node)\n",
    "\n",
    "\n",
    "        if left_head and not right_head:\n",
    "            node.right = next_node\n",
    "            next_node.left = node\n",
    "            return left_head\n",
    "\n",
    "        if not left_head and right_head:\n",
    "            node.right = right_head\n",
    "            right_head.left = node\n",
    "            return node\n",
    "\n",
    "        if left_head and right_head:\n",
    "            node.right = right_head \n",
    "            right_head.left = node\n",
    "            return left_head\n",
    "\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return None \n",
    "\n",
    "        dummy = Node(-1)\n",
    "        head = self.helper(root, dummy)\n",
    "        head.left = dummy.left \n",
    "        dummy.left.right = head \n",
    "        return head\n",
    "\n",
    "    # def helper(self, node: 'Optional[Node]', pre_node: 'Optional[Node]'):\n",
    "    #     if not node:\n",
    "    #         return None\n",
    "    #     if not node.left and not node.right:\n",
    "    #         if pre_node.val < node.val:\n",
    "    #             node.left = pre_node\n",
    "    #             pre_node.right = node\n",
    "\n",
    "    #         if pre_node.val > node.val:\n",
    "    #             node.right = pre_node\n",
    "    #             pre_node.left = node\n",
    "\n",
    "    #         return node\n",
    "\n",
    "    #     left_head = self.helper(node.left, node)\n",
    "    #     right_tail = self.helper(node.right, node)\n",
    "\n",
    "\n",
    "    #     if left_head:\n",
    "    #         if pre_node.val < left_head.val:\n",
    "    #             pre_node.right = left_head\n",
    "    #             left_head.left = pre_node\n",
    "    #             return right_tail if right_tail else node\n",
    "    #         elif not right_tail: \n",
    "    #             pre_node.left = node\n",
    "    #             node.right = pre_node\n",
    "    #             return left_head \n",
    "\n",
    "    #     if right_tail:\n",
    "    #         if pre_node.val > right_tail.val:\n",
    "    #             pre_node.left = right_tail\n",
    "    #             right_tail.right = pre_node\n",
    "    #             return left_head  if left_head else node \n",
    "    #         elif not left_head:\n",
    "    #             pre_node.right = node\n",
    "    #             node.left = pre_node\n",
    "    #             return right_tail \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     if not root:\n",
    "    #         return None\n",
    "\n",
    "    #     head = self.helper(root.left, root)\n",
    "    #     tail = self.helper(root.right, root)\n",
    "\n",
    "\n",
    "    #     if head and tail:\n",
    "    #         head.left = tail\n",
    "    #         tail.right = head\n",
    "\n",
    "    #     if head and not tail:\n",
    "    #         head.left = root\n",
    "    #         root.right = head \n",
    "\n",
    "    #     if not head and tail:\n",
    "    #         root.left = tail \n",
    "    #         tail.right = root\n",
    "        \n",
    "    #     if not head and not tail:\n",
    "    #         root.left = root \n",
    "    #         root.right = root\n",
    "\n",
    "\n",
    "    #     return head if head else root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        # 先进行一次中序遍历\n",
    "        inorder = []\n",
    "        def dfs(node: Node):\n",
    "            if node is None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            inorder.append(node)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        # 再进行拼装\n",
    "        \n",
    "        for i, node in enumerate(inorder):\n",
    "            if i > 0:\n",
    "                inorder[i].left = inorder[i-1]\n",
    "            if i < len(inorder) - 1:\n",
    "                inorder[i].right = inorder[i+1]\n",
    "        \n",
    "        first, last = inorder[0], inorder[-1]\n",
    "        first.left = last\n",
    "        last.right = first\n",
    "        return inorder[0]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
